package xio.leetcode.java;

import xio.leetcode.java.base.ListNode;
import xio.leetcode.java.test.LinkedListUtils;

/**
 * 141. Linked List Cycle (Easy)
 * 给定一个链表，判断链表中是否有环。
 *
 * 思路：双指针遍历，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇；
 */
public class LC141_HasCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode l1 = head, l2 = head.next;
        while (l1 != null && l2 != null && l2.next != null) {
            if (l1 == l2) {
                return true;
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;
    }

    public static void main(String[] args) {
        // 生成有环链表
        ListNode head = LinkedListUtils.generateLinkedList(true,3,2,4);
        LC141_HasCycle hc = new LC141_HasCycle();

        System.out.println(hc.hasCycle(head));
    }
}
